package cn.jdemo.algorithm.sort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;
import java.util.Collections;

/**
 * 归并排序
 *  (1) 左右排序
 *  (2) 然后归并
 *
 * @date 2020/12/25
 */
public class Demo01_MergeSort {
    private static final Logger logger = LoggerFactory.getLogger(Demo01_MergeSort.class);

    private static int[] tmp;

    public static void main(String[] args) {
        int[] arrs = new int[]{6,5,4,9,10,3,1,2,0};
        // 先给辅助数组开辟内存空间
        tmp = new int[arrs.length];
        System.out.println("before mergeSort:"+ Arrays.toString(arrs));
        mergeSort(arrs,0,arrs.length-1);
        System.out.println("after mergeSort:"+ Arrays.toString(arrs));
    }

    public static void mergeSort(int[] nums, int left, int right){
        if(left >= right){
            return;
        }
        int mid = ((right-left) >> 1) + left;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        merge(nums,left,mid,right);
    }

    private static void merge(int[] nums, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            tmp[i] = nums[i];
        }

        int j = left;
        int k = mid + 1;
        System.out.println("归并前:"+Arrays.toString(nums));
        for (int i = left; i <=right; i++) {
            if (j == mid+1){
                nums[i] = tmp[k]++;
            }else if (k == right+1){
                nums[i] = tmp[j++];
            }else if(tmp[j] <= tmp[k]){
                nums[i] = tmp[j++];
            }else if(tmp[j] > tmp[k]){
                nums[i] = tmp[k++];
            }
        }
        System.out.println("归并后:"+Arrays.toString(nums));
    }
}
